package demo22;


/**
 * 优美的排列
 * https://leetcode.cn/problems/beautiful-arrangement/
 */


class Solution {
    int ret = 0;
    boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(1, n);
        return ret;
    }
    public void dfs(int pos, int n) {
        if(pos == n + 1) {
            ret++;
            return;
        }
        for(int i = 1; i <= n; i++) {
            if(!check[i] && (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
                dfs(pos + 1, n);
                check[i] = false; // 恢复现场
            }
        }
    }
}